package likou;

import java.util.*;

public class _538 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(1);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.left.right.right = new TreeNode(3);
        root.right = new TreeNode(6);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        root.right.right.right = new TreeNode(8);


        convertBST(root);
    }

    static Map<Integer, Integer> map = new HashMap<>();

    public static TreeNode convertBST(TreeNode root) {
        dfs(root);
        List<Integer> list = new ArrayList<>(map.keySet());
        list.sort(Comparator.comparingInt(l -> l));
        int sum = 0;
        Map<Integer, Integer> map2 = new HashMap<>();
        for (int i = list.size() - 1; i >= 0; i--) {
            sum += map.get(list.get(i)) * list.get(i);
            map2.put(list.get(i), sum);
        }
        dfs(root,map2);
        return root;
    }

    public static void dfs(TreeNode root) {
        if (root == null) return;
        map.merge(root.val, 1, Integer::sum);
        dfs(root.left);
        dfs(root.right);
    }

    public static void dfs(TreeNode root, Map<Integer, Integer> map2) {
        if (root == null) return;
        root.val = map2.get(root.val);
        dfs(root.left, map2);
        dfs(root.right, map2);
    }



    int sum = 0;
    public TreeNode convertBST2(TreeNode root) {
        if (root == null) {
            return null;
        }
        convertBST2(root.right);
        sum+= root.val;
        root.val = sum;
        convertBST2(root.left);
        return root;
    }
}
